package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

/**
 * 插入排序
 */
public class InsertSort {
    /**
     * 将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列
     * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置
     * 默认由小到大排序
     * @param array 原数组，执行完后数组内容改变
     */
    public static void insertSort(int[] array) {
        ArrayUtils.printArray(array, 0);
        // 最多排序 (array.length - 1) 趟
        for (int i = 1; i < array.length; i++) {
            // 记录每轮需要比较插入的数
            int x = array[i];
            int j = i;
            while (j > 0 && x < array[j - 1]) {
                // 从后往前比较
                // 元素逐个后移，直到 j 为 x 待插入的位置
                array[j] = array[j - 1];
                j--;
            }
            if (j != i) {
                array[j] = x;
            }
            ArrayUtils.printArray(array, i);
        }
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        insertSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        insertSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        insertSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }
}
